"""
难度：简单
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = "a", magazine = "b"
输出：false
示例 2：
输入：ransomNote = "aa", magazine = "ab"
输出：false
示例 3：
输入：ransomNote = "aa", magazine = "aab"
输出：true
"""

"""
暴力做法是双重循环遍历字符串 ransomNote 和 magazine。我们可以用哈希表来减少算法的时间复杂度。具体做法如下：
先用哈希表存储 magazine 中各个字符的个数（哈希表可用字典或数组实现）。
再遍历字符串 ransomNote 中每个字符，对于每个字符：
如果在哈希表中个数为 0，直接返回 False。
如果在哈希表中个数不为 0，将其个数减 1。
遍历到最后，则说明 ransomNote 能由 magazines 里面的字符构成。返回 True。

"""

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        magazine_counts = [0 for _ in range(26)]

        for ch in magazine:
            num = ord(ch) - ord("a")
            magazine_counts[num] += 1
        
        for ch in ransomNote:
            num = ord(ch) - ord("a")
            if magazine_counts[num] == 0:
                return False
            else:
                magazine_counts[num] -= 1
        return True

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        if len(ransomNote) > len(magazine):
            return False
            
        return not collections.Counter(ransomNote) - collections.Counter(magazine)